﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            //Console.WriteLine(DateTime.Now.ToString("HH:mm:ss.ffffff"));
            //var cj = ScimTable.Load("CangJie3.txt");
            //Console.WriteLine(DateTime.Now.ToString("HH:mm:ss.ffffff"));
            //var zy = ScimTable.Load("ZhuYin-Big.txt");
            //Console.WriteLine(DateTime.Now.ToString("HH:mm:ss.ffffff")); 
            //Console.ReadLine();


            var rnd = new Random();
            var list = new List<int>();
            for (var i = 0; i < 100; i++)
                list.Add(i);
            for (var i = 0; i < list.Count; i++)
            {
                var r = rnd.Next(i, list.Count);
                var t = list[r];
                list[r] = list[i];
                list[i] = t;
            }
            var tree = new Tree<int, int>();
            foreach (var i in list)
            {
                tree.Insert(i, i);
            }
            Console.ReadLine();
            Console.WriteLine(tree);
            while (true)
            {
                var node = tree.Search(29);
                Console.WriteLine("{0}: {1}", node.Key, node.Value);
                Console.ReadLine();
            }
        }
    }


    public class Node<TKey, TValue>
    {
        public const int Red = 0;
        public const int Black = 1;
        public TKey Key;
        public TValue Value;
        public int Color;
        public Node<TKey, TValue> Left;
        public Node<TKey, TValue> Right;
        public Node<TKey, TValue> Parent;

        public Node(TKey key, TValue value)
        {
            Key = key;
            Value = value;
            Color = Red;
        }
        public override string ToString()
        {
            var status = 0;
            if (Left == null) status += 1;
            if (Right == null) status += 2;
            const string pattern = "{0}({1}, {2})";
            switch (status)
            {
                case 3: return Key.ToString();
                case 2: return string.Format(pattern, Key, Left, "_");
                case 1: return string.Format(pattern, Key, "_", Right);
                default: return string.Format(pattern, Key, Left, Right);
            }
        }
    }
    public class Tree<TKey, TValue> where TKey : IComparable
    {
        private Node<TKey, TValue> _root;
        private int _count;
        public int Count { get { return _count; } }
        public Tree()
        {
            _root = null;
            _count = 0;
        }
        private static void KillTree(ref Node<TKey, TValue> node)
        {
            if (node == null) return;
            KillTree(ref node.Left);
            KillTree(ref node.Right);
            node = null;
        }
        public void Clear()
        {
            KillTree(ref _root);
            _count = 0;
        }
        public Node <TKey, TValue> Search(TKey key)
        {
            var node = _root;
            while (node != null)
            {
                Console.WriteLine("Search: {0}", node.Key);
                var comp = key.CompareTo(node.Key);
                if (comp == 0) return node;
                node = comp < 0 ? node.Left : node.Right;
            }
            return null;
        }
        private static void Add(Node<TKey, TValue> node, ref Node<TKey, TValue> tree)
        {
            if (tree == null)
            {
                tree = node;
                return;
            }
            var comp = node.Key.CompareTo(tree.Key);
            if (comp == 0) return; // is exists
            if (comp < 0) Add(node, ref tree.Left);
            else Add(node, ref tree.Right);
        }
        public Node<TKey, TValue> Insert(TKey key, TValue value)
        {
            var node = new Node<TKey, TValue>(key, value);
            try
            {
                if (_root == null) _root = node;
                else Add(node, ref _root);
                _count++;
                return node;
            }
            catch (Exception)
            {
                return null;
            }
        }
        private Node<TKey, TValue> FindParent(TKey key, ref Node<TKey, TValue> parent)
        {
            var node = _root;
            parent = null;
            while (node != null)
            {
                var comp = key.CompareTo(node.Key);
                if (comp == 0) return node;
                parent = node;
                node = comp < 0 ? node.Left : node.Right;
            }
            return null;
        }
        private static Node<TKey, TValue> FindSuccessor(Node<TKey, TValue> startNode, ref Node<TKey, TValue> parent)
        {
            parent = startNode;
            startNode = startNode.Right;
            while (startNode.Left != null)
            {
                parent = startNode;
                startNode = startNode.Left;
            }
            return startNode;
        }
        public void Delete(TKey key)
        {
            Node<TKey, TValue> parent = null;
            var nodeToDelete = FindParent(key, ref parent);
            if (nodeToDelete == null)
                throw new Exception("Unable to delete node: " + key);
            if (nodeToDelete.Left == null && nodeToDelete.Right == null)
            {
                if (parent == null)
                {
                    _root = null;
                    return;
                }
                if (parent.Left == nodeToDelete) parent.Left = null;
                else parent.Right = null;
                _count--;
                return;
            }
            if (nodeToDelete.Left == null)
            {
                if (parent == null)
                {
                    _root = nodeToDelete.Right;
                    return;
                }
                if (parent.Left == nodeToDelete) parent.Right = nodeToDelete.Right;
                else parent.Left = nodeToDelete.Right;
                _count--;
                return;
            }
            if (nodeToDelete.Right == null)
            {
                if (parent == null)
                {
                    _root = nodeToDelete.Left;
                    return;
                }
                if (parent.Left == nodeToDelete) parent.Left = nodeToDelete.Left;
                else parent.Right = nodeToDelete.Left;
                _count--;
                return;
            }
            var successor = FindSuccessor(nodeToDelete, ref parent);
            var tmp = new Node<TKey, TValue>(successor.Key, successor.Value);
            if (parent.Left == successor) parent.Left = null;
            else parent.Right = null;
            nodeToDelete.Key = tmp.Key;
            nodeToDelete.Value = tmp.Value;
            _count--;
        }
        public override string ToString()
        {
            return string.Format("{0}", _root);
        }
    }


    [Serializable]
    public class ScimItem
    {
        public string Key { get; set; }
        public string Word { get; set; }
        public int Weight { get; set; }
    }
    [Serializable]
    public class ScimTree : Dictionary<char, ScimTree>
    {
        public ScimTree Parent { get; private set; }
        public char Key { get; set; }
        public ScimItem Item { get; set; }

        public ScimTree(ScimTree parent, char key)
        {
            Parent = parent;
            Key = key;
        }
        public ScimTree Search(string key)
        {
            return Search(key, 0);
        }
        public ScimTree Search(string key, int index)
        {
            if (index >= key.Length) return null;
            if (key == Item.Key) return this;
            return ContainsKey(key[index]) ? this[key[index]].Search(key, index + 1) : null;
        }
        protected void Add(ScimItem item, int deep)
        {
            var key = item.Key[deep];
            if (!ContainsKey(key))
                Add(key, new ScimTree(this, key));
            this[key].Add(item, deep+1);
        }
    }
    [Serializable]
    public class ScimTable : ScimTree
    {
        public readonly Dictionary<string, string> Definition;
        public readonly Dictionary<string, string> CharPrompts;
        public ScimTable()
            : base(null, (char)0x00)
        {
            Definition = new Dictionary<string, string>();
            CharPrompts = new Dictionary<string, string>();
        }
        //public string UUID { get; set; }
        //public string SerialNumber { get; set; }
        //public string Icon { get; set; }
        //public string Name { get; set; }
        //public List<string> LocalNames { get; set; }
        //public string Author { get; set; }
        //public List<string> Languages { get; set; }
        //public string StatusPrompt { get; set; }
        //public string KeyboardLayout { get; set; }
        //public bool AutoSelect { get; set; }
        //public bool AutoWildcard { get; set; }
        //public bool AutoCommit { get; set; }
        //public bool AutoSplit { get; set; }
        //public bool DynamicAdjust { get; set; }
        //public bool AutoFill { get; set; }
        //public bool AlwaysShowLookup { get; set; }
        //public bool UseFullWidthPunctuationByDefault { get; set; }
        //public bool UseFillWidthLetterByDefualt { get; set; }
        //public int MaxKeyLength { get; set; }
        //public bool ShowKeyPrompt { get; set; }
        public void AddItem(string raw)
        {
            var list = raw.Split(' ', '\t');
            var item = new ScimItem();
            if (list.Length > 1)
            {
                item.Key = list[0];
                item.Word = list[1];
            }
            if (list.Length > 2)
            {
                int w;
                if (int.TryParse(list[2], out w))
                    item.Weight = w;
            }
            
            
        }
        public static ScimTable Load(string path)
        {
            var parser = new ScimTableParser();
            return parser.Parse(path);
        }
    }
    public class ScimTableParser
    {
        private const string Remark = "###";
        private const string BeginDefinition = "BEGIN_DEFINITION";
        
        private const string BeginCharPrompts = "BEGIN_CHAR_PROMPTS_DEFINITION";
        private const string EndCharPrompts = "END_CHAR_PROMPTS_DEFINITION";
        
        private const string EndDefinition = "END_DEFINITION";
        private const string BeginTable = "BEGIN_TABLE";
        private const string EndTable = "END_TABLE";

        private readonly List<char> _list;
        private Action<string> _p;
        private ScimTable _table;
        public ScimTableParser()
        {
            _list = new List<char>();
            _p = FindHeader;
        }
        public ScimTable Parse(string path)
        {
            _list.Clear();
            _p = FindHeader;
            _table = new ScimTable();
            using (var f = new StreamReader(path))
            {
                while (true)
                {
                    var line = f.ReadLine();
                    if (line == null) break;
                    ParseLine(line);
                }
            }
            return _table;
        }
        private void ParseLine(string line)
        {
            if (_p != null) _p(line);
        }
        private void FindHeader(string line)
        {
            if (string.IsNullOrEmpty(line)) return;
            if (line.StartsWith(BeginDefinition)) _p = ReadDefinition;
        }
        private void ReadDefinition(string line)
        {
            if (string.IsNullOrEmpty(line)) return;
            if (line.StartsWith(Remark)) return;
            if (line.StartsWith(BeginCharPrompts))
            {
                _p = ReadCharPrompts;
                return;
            }
            if (line.StartsWith(EndDefinition))
            {
                _p = FindTableHeader;
                return;
            }
            var index = line.IndexOf(" = ");
            if (index > -1)
                _table.Definition[line.Substring(0, index)] = line.Substring(index + 3);
        }
        private void ReadCharPrompts(string line)
        {
            if (string.IsNullOrEmpty(line)) return;
            if (line.StartsWith(Remark)) return;
            if (line.StartsWith(EndCharPrompts))
            {
                _p = ReadDefinition;
                return;
            }
            var index = line.IndexOf(' ');
            if (index > -1)
                _table.CharPrompts[line.Substring(0, index)] = line.Substring(index+1);
        }
        private void FindTableHeader(string line)
        {
            if (string.IsNullOrEmpty(line)) return;
            if (line.StartsWith(BeginTable))
                _p = ReadTableRow;
        }
        private void ReadTableRow(string line)
        {
            if (string.IsNullOrEmpty(line)) return;
            if (line.StartsWith(Remark)) return;
            if (line.StartsWith(EndTable))
            {
                _p = JobCompleted;
                return;
            }
            _table.AddItem(line);
        }
        private static void JobCompleted(string line) { }
    }
}
